import java.util.*;

public class FindKSmallestNumbers {
    public static List<Integer> getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr == null || arr.length == 0) {
            return new ArrayList<>();
        }

        if (k >= arr.length) {
            List<Integer> result = new ArrayList<>();
            for (int num : arr) {
                result.add(num);
            }
            return result;
        }

       // 使用一个大小为 k 的最大堆，通过自定义比较器来创建最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1; // 将 o1 和 o2 反向比较，构建最大堆
            }
        });

        for (int num : arr) {
            if (maxHeap.size() < k) {
                maxHeap.offer(num);
            } else {
                if (num < maxHeap.peek()) {
                    maxHeap.poll();
                    maxHeap.offer(num);
                }
            }
        }

        // 将堆中的元素存入结果列表
        List<Integer> result = new ArrayList<>(maxHeap);
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 1, 6, 2, 7, 3, 8};
        int k = 4;
        List<Integer> leastNumbers = getLeastNumbers(arr, k);
        System.out.println(leastNumbers); // 输出可能是 [1, 2, 3, 4]
    }
}
